home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 6869 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.7 KB
  1. Path: ntc.nokia.com!usenet
  2. From: Risto Lankinen <risto.lankinen@ntc.nokia.com>
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 20 Feb 1996 07:17:47 GMT
  6. Organization: Nokia Telecommunications
  7. Message-ID: <4gbsir$opr@axl02it.ntc.nokia.com>
  8. References: <4fr8be$ass@news.iconn.net> <4g0giv$94s@sun132.spd.dsccc.com>
  9. NNTP-Posting-Host: pc-rlankinen.ntc.nokia.com
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 1.2N (Windows; I; 16bit)
  14.  
  15. Hi!
  16.  
  17. kcline@sun132.spd.dsccc.com (Kevin Cline) wrote:
  18. >In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net>
  19. >wrote:
  20. >>Here is what I am trying to do, I want to find the last NON-ZERO digit
  21. >>of a given factorial.  For instance,
  22. >>
  23. >>5! = 120
  24. >>
  25. >>so the last non-zero digit is 2. ...
  26.  
  27.    [a suggested solution deleted]
  28.  
  29. >This solution runs in O(n).  With a bit more thought a log(n) solution
  30. >is possible.
  31.  
  32. There is an algorithm that calculates the last non-zero _binary_ digit
  33. of ANY factorial - with SUB-LOGARITHMIC time even in the worst case!!!
  34.  
  35. Mail me if interested but be prepared to explain what you need it for.
  36. The algorithm is indeed very VERY fast, and so I don't want to give it
  37. away without being credited at least.  Also, please mention "rightmost
  38. non-zero binary digit algorithm" in your request.
  39.  
  40. terv: Risto
  41.  
  42. -- 
  43. Risto Lankinen / System Engineer  ***************************************
  44. Nokia Telecommunications,         *  2                              2   *
  45. Cellular Data; Helsinki, Finland. * 2 -1 is PRIME!  Now working on 2 +1 *
  46. risto.lankinen@ntc.nokia.com      ***************************************
  47.  
  48.  
  49.